#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int paintWalls(vector<int>& cost, vector<int>& time) {
        long long n = cost.size(), ret = INT_MAX;
        vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, INT_MAX));
        dp[0][0] = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j <= n; j++) {
                // dp[i][j] = dp[i - 1][j];
                // if(j - time[i - 1] - 1 >= 0) dp[i][j] = min(dp[i][j], dp[i - 1][j - time[i - 1] - 1] + cost[i - 1]);
                if (dp[i][j] != INT_MAX) {
                    dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
                    if (j + 1 + time[i] > n) ret = min(ret, dp[i][j] + cost[i]);
                    else dp[i + 1][j + 1 + time[i]] = min(dp[i + 1][j + 1 + time[i]], dp[i][j] + cost[i]);
                }
            }
        // for(int i = 0; i <= n; i++){
        //     for(int j = 0; j <= n; j++) cout << dp[i][j] << ' ';
        //     cout << endl;
        // }
        for (int i = 1; i <= n; i++) ret = min(ret, dp[i][n]);
        return ret;
    }
};